#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;

class MedianFinder1 {
public:
    vector<int> bigRootHeap;
    vector<int> smallRootHeap;
public:
    void test() {
        vector<int> v;
        //大根堆
        make_heap(v.begin(),v.end(),less<int>());
        v.push_back(1);
        push_heap(v.begin(),v.end(),less<int>());
        v.push_back(2);
        push_heap(v.begin(),v.end(),less<int>());
        v.push_back(3);
        push_heap(v.begin(),v.end(),less<int>());
        v.push_back(4);
        push_heap(v.begin(),v.end(),less<int>());
        for(int i=0; i<v.size(); i++) {
            cout << v[i] << " ";
        }
        cout << endl;
        cout << "back:" << v.back() << endl;
        cout << "front:" << v.front() << endl;
        cout << "remove big root heap root value:" << v.front() << endl;
        pop_heap(v.begin(),v.end(),less<int>());
        v.pop_back();
        for(int i=0; i<v.size(); i++) {
            cout << v[i] << " ";
        }
        cout << endl;
        cout << "back:" << v.back() << endl;
        cout << "front:" << v.front() << endl;
    }
    MedianFinder1() {
        make_heap(bigRootHeap.begin(),bigRootHeap.end(),less<int>());
        make_heap(smallRootHeap.begin(),smallRootHeap.end(),greater<int>());
    }
    
    void addNum1(int num) {
        int bsize = bigRootHeap.size();
        int ssize = smallRootHeap.size();
        //小根堆最小值 >= 大根堆最大值
        if(bsize <= ssize) {
            //打算放到大根堆
            bigRootHeap.push_back(num);
            push_heap(bigRootHeap.begin(),bigRootHeap.end(),less<int>());
            bsize++;
        } else {
            smallRootHeap.push_back(num);
            push_heap(smallRootHeap.begin(),smallRootHeap.end(),greater<int>());
            ssize++;
        }
        if(bsize && ssize) {
            //两个堆都有元素 验证是否交换
            int broot = bigRootHeap.front();
            int sroot = smallRootHeap.front();
            if(broot > sroot) {
                //交换两个堆的堆顶
                //更新大根堆堆顶元素
                pop_heap(bigRootHeap.begin(),bigRootHeap.end(),less<int>());
                bigRootHeap.pop_back();
                bigRootHeap.push_back(sroot);
                push_heap(bigRootHeap.begin(),bigRootHeap.end(),less<int>());
                //更新小根堆堆顶元素
                pop_heap(smallRootHeap.begin(),smallRootHeap.end(),greater<int>());
                smallRootHeap.pop_back();
                smallRootHeap.push_back(broot);
                push_heap(smallRootHeap.begin(),smallRootHeap.end(),greater<int>());
            }
        }
    }

    void addNum(int num) {
        if(bigRootHeap.size()) {
            int bigRoot = bigRootHeap.front();
            //小根堆最小值 >= 大根堆最大值
            if(num <= bigRoot) {
                //当前数字小于大根堆堆顶,入大根堆
                bigRootHeap.push_back(num);
                push_heap(bigRootHeap.begin(),bigRootHeap.end(),less<int>());
            } else {
                smallRootHeap.push_back(num);
                push_heap(smallRootHeap.begin(),smallRootHeap.end(),greater<int>());
            }
            //平衡两个堆
            balanceHeap(bigRootHeap,smallRootHeap);
        } else {
            //第一个数字直接入大根堆
            bigRootHeap.push_back(num);
            push_heap(bigRootHeap.begin(),bigRootHeap.end(),less<int>());
        }
    }
    

    void balanceHeap(vector<int>& bigRootHeap,vector<int>& smallRootHeap) {
        int bsize = bigRootHeap.size();
        int ssize = smallRootHeap.size();    
        if(bsize - ssize > 1) {
            int broot = bigRootHeap.front();
            //大根堆堆顶移到小根堆
            //移除大根堆堆顶
            pop_heap(bigRootHeap.begin(),bigRootHeap.end(),less<int>());
            bigRootHeap.pop_back();
            //将其移入小根堆
            smallRootHeap.push_back(broot);
            push_heap(smallRootHeap.begin(),smallRootHeap.end(),greater<int>());
        } else if(ssize - bsize > 1) {
            int sroot = smallRootHeap.front();
            //小根堆堆顶移到大根堆
            //移除小根堆堆顶
            pop_heap(smallRootHeap.begin(),smallRootHeap.end(),greater<int>());
            smallRootHeap.pop_back();
            //移入到大根堆
            bigRootHeap.push_back(sroot);
            push_heap(bigRootHeap.begin(),bigRootHeap.end(),less<int>());
        }
    }
    double findMedian() {
        int bsize = bigRootHeap.size();
        int ssize = smallRootHeap.size();
        if(bsize == ssize) {
            //共计偶数个元素 取平均值
            double ret = (bigRootHeap.front()+smallRootHeap.front());
            return ret/2;
        } else {
            //共计奇数个元素
            cout << "bsize:" << bsize << endl;
            cout << "ssize:" << ssize << endl;
            for(int i=0; i<bigRootHeap.size(); i++) {
                cout << bigRootHeap[i] << " ";
            }
            cout << endl;
            cout << "bfront:" << bigRootHeap.front() << endl;
            double ret;
            if(bsize > ssize) {
                ret = bigRootHeap.front();
            } else {
                ret = smallRootHeap.front();
            }
            // double ret = bigRootHeap.front() ? bsize > ssize : smallRootHeap.front();
            return ret;
        }
    }
};

class MedianFinder {
public:
    priority_queue<int,vector<int>,less<int>> bigRootHeap;
    priority_queue<int,vector<int>,greater<int>> smallRootHeap;
public:
    MedianFinder() {

    }
    
    void addNum(int num) {
        //将新数据入堆
        if(bigRootHeap.size() == 0) {
            //第一个直接入大根堆
            bigRootHeap.push(num);
        } else {
            if(num < bigRootHeap.top()) {
                bigRootHeap.push(num);
            } else {
                smallRootHeap.push(num);
            }
        }
        //平衡两个堆
        balanceHeap();
    }

    void balanceHeap() {
        int bsize = bigRootHeap.size();
        int ssize = smallRootHeap.size();
        if(bsize - ssize > 1) {
            //大根堆堆顶元素移动到小根堆
            int broot = bigRootHeap.top();
            bigRootHeap.pop();
            smallRootHeap.push(broot);
        } else if(ssize - bsize > 1) {
            //小根堆堆顶元素移动到大根堆
            int sroot = smallRootHeap.top();
            smallRootHeap.pop();
            bigRootHeap.push(sroot);
        }
    }
    
    double findMedian() {
        int bsize = bigRootHeap.size();
        int ssize = smallRootHeap.size();
        if(bsize == ssize) {
            double ret = (bigRootHeap.top()+smallRootHeap.top());
            return ret/2;
        } else if(bsize < ssize) {
            return smallRootHeap.top();
        } else {
            return bigRootHeap.top();
        }
    }
};

int main() {
    MedianFinder1().test();
    return 0;
}